package com.cruelbb.wonderful2025.algo.search;

public class BinarySearch {

    //二分查找
    public static int binarySearch(int[] nums, int target) {
        //i j 先指向 数组的 首和尾
        int i = 0;
        int j = nums.length - 1;
        //循环起来 设置一个结束条件
        while (i <= j) {
            //计算中点
            int m = i + (j - i) / 2;
            //比较 m 与 target的大小
            if (nums[m] == target) {
                return m;
            } else if (nums[m] > target) {
                j = m - 1;
            } else {
                i = m + 1;
            }
        }
        return -1;
    }


    /**
     * 数组不存在重复元素。
     * 现将 target 插入数组 nums 中，并保持其有序性。
     * 若数组中已存在元素 target ，则插入到其左方。请返回插入后 target 在数组中的索引。
     */
    public static int binarySearchInsert(int[] nums, int target) {
        int i = 0;
        int j = nums.length - 1;
        while (i <= j) {
            int m = i + (j - i) / 2;
            if (nums[m] == target) {
                return m - 1;
            } else if (nums[m] > target) {
                j = m - 1;
            } else {
                i = m + 1;
            }
        }
        return i;
    }


    /**
     * 数组存在重复元素。
     */
    public static int binarySearchInsert2(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                right = mid - 1;
            } else if (nums[mid] > target) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }

        return left;
    }

    /**
     * 寻找左边界
     */
    public static int binarySearchLeftEdge(int[] nums, int target) {
        int left = binarySearchInsert2(nums, target);
        if (left == nums.length || nums[left] != target) {
            return -1;
        }
        return left;
    }

    /**
     * 寻找左边界
     */
    public static int binarySearchRightEdge(int[] nums, int target) {
        int leftEdge = binarySearchLeftEdge(nums, target + 1);
        int rightEdge =  leftEdge - 1;
        if (rightEdge == -1 || nums[rightEdge] != target) {
            return -1;
        }
        return rightEdge;
    }
}

